#include "BinaryTree.h"
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
struct BinaryTreeNode
{
    BTNode *parent;
    BTNode *left;
    BTNode *right;
    ElementType data;
};

BTNode *CreateBTNode(ElementType element)
{
    BTNode *node = (BTNode*)malloc(sizeof(BTNode));
    if(node == NULL)
        return NULL;

    node->data = element;
    node->left = node->right = node->parent = NULL;
    return node;
}

struct BinarySortTree
{
    BTNode *root;
};



BSTree *InitBSTree()
{
    BSTree *tree = (BSTree*)malloc(sizeof(BSTree));
    if(tree == NULL)
        return NULL;
    tree->root = NULL;
    return tree;
}

void InsertNodeElement(BTNode *node,ElementType element)
{
    if(node == NULL)
        return;
    
    if(node->data > element && node->left == NULL)
    {
        node->left = CreateBTNode(element);
        if(node->left == NULL)
            return;
        node->left->parent = node;
        return;
    }
    if(node->data < element && node->right == NULL)
    {
        node->right = CreateBTNode(element);
        if(node->right == NULL)
            return;
        node->right->parent = node;
        return;
    }
    if(node->data == element)
        return;
    if(node->data > element)
        InsertNodeElement(node->left,element);
    if(node->data < element)
        InsertNodeElement(node->right,element);
}
void InsertElement(BSTree *tree, ElementType element)
{
    if(tree->root == NULL)
        tree->root = CreateBTNode(element);
    else
        InsertNodeElement(tree->root,element);
}

void TravelNodePrev(BTNode *node)
{
    if(node == NULL)
        return;
    printf("%d ",node->data);
    TravelNodePrev(node->left);
    TravelNodePrev(node->right);
}
void TravelPrev(BSTree *tree)
{
    TravelNodePrev(tree->root);
}

void TravelNodeMid(BTNode *node)
{
    if(node == NULL)
        return;
    TravelNodeMid(node->left);
    printf("%d ",node->data);
    TravelNodeMid(node->right);
}
void TravelMid(BSTree *tree)
{
    TravelNodeMid(tree->root);
}

void TravelNodePost(BTNode *node)
{
    if(node == NULL)
        return;
    TravelNodePost(node->left);
    TravelNodePost(node->right);
    printf("%d ",node->data);
}
void TravelPost(BSTree *tree)
{
    TravelNodePost(tree->root);
}

BTNode *FindNodeElement(BTNode *node,ElementType element)
{
    if(node == NULL)
        return NULL;
    if(node->data == element)
        return node;
    else if(node->data > element)
        FindNodeElement(node->left,element);
    else
        FindNodeElement(node->right,element);
}
BTNode *FindByElement(BSTree *tree, ElementType element)
{
    return FindNodeElement(tree->root,element);
}

bool IsLeftChild(BTNode *parent,BTNode *child)
{
    if(parent->left == child)
        return true;
    return false;
}

void RemoveByElement(BSTree *tree, ElementType element)
{
    BTNode *node = FindByElement(tree,element);
    if(node == NULL)
        return;
    
    if(node->left == NULL && node->right == NULL)
    {
        if(node->parent == NULL)
        {
            free(node);
            tree->root = NULL;
            return;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = NULL;
        else
            node->parent->right = NULL;
        free(node);
    }
    else if(node->left == NULL)
    {
        node->right->parent = node->parent;
        if(node->parent == NULL)
        {
            tree->root = node->right;
            free(node);
            return;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->right;
        else
            node->parent->right = node->right;
        free(node);
    }
    else if(node->right == NULL)
    {
        node->left->parent = node->parent;
        if(node == NULL)
        {
            tree->root = node->left;
            free(node);
            return;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->left;
        else
            node->parent->right = node->left;
        free(node);
    }
    else
    {
        BTNode *MinNode = node->right;
        while(MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }
        node->data = MinNode->data;
        if(node->right == MinNode)
            node->right = MinNode->right;
        else
            MinNode->parent->left = MinNode->left;
        free(MinNode);
    }
}


int GetNumber(BTNode *node)
{
    if(node == NULL)
        return 0;
    
    //节点数量 = 左子树节点个数 + 右子树节点个数 + 1;
    return GetNumber(node->left) + GetNumber(node->right) + 1;
}

//获得树中节点数量
int GetNodeNumber(BSTree *tree)
{
    return GetNumber(tree->root);
}


BTNode *RotateLeft(BTNode *node)
{
    BTNode *t = node->right;
    
    t->parent = node->parent;
    node->right = t->left;
    t->left = node;
    node->parent = t;
    if(node->right != NULL)
        node->right->parent = node;
    

    return t;
}

BTNode *RotateRight(BTNode *node)
{
    if(node->left == NULL)
    {

    }
    BTNode *t = node->left;
    t->parent = node->parent;
    node->left = t->right;
    t->right = node;
    node->parent = t;
    t->right->parent = node;
    return t;
}

BTNode *RotateLeftRight(BTNode *node)
{
    node->left = RotateLeft(node->left);
    return RotateRight(node);
}

BTNode *RotateRightLeft(BTNode *node)
{
    node->right = RotateRight(node->right);
    return RotateLeft(node);
}

int GetNodeHeight(BTNode *node)
{
    if(node == NULL)
        return 0;
    
    int leftHeight = GetNodeHeight(node->left);
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int GetTreeHeight(BSTree *tree)
{
    if(tree->root == NULL)
        return 0;
    
    int leftHeight = GetNodeHeight(tree->root->left);
    int rightHeight = GetNodeHeight(tree->root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}


BTNode *InsertNode(BTNode *node,ElementType element)
{
    if(node == NULL)
    {
        //node = CreateBTNode(element);
        return node;
    }
        
    if(node->data > element && node->left == NULL)
    {
        node->left = CreateBTNode(element);
        if(node->left == NULL)
            return node;
        node->left->parent = node;
        
        return node;
    }
    if(node->data < element && node->right == NULL)
    {
        node->right = CreateBTNode(element);
        if(node->right == NULL)
            return node;
        node->right->parent = node;
       
        return node;
    }
    // if(node->data == element)
    //     return node;
    if(node->data > element)
    {
        node->left = InsertNode(node->left,element);
        if(GetNodeHeight(node->left) - GetNodeHeight(node->right) > 1)
        {
            //左左插入
            if(node->left->data > element)
                node = RotateRight(node);
            //左右插入
            else
                node = RotateLeftRight(node);  
        }
    }
        
    if(node->data < element)
    {
        node->right = InsertNode(node->right,element);
        if(GetNodeHeight(node->right) - GetNodeHeight(node->left) > 1)
        {
            //右右插入
            if(node->right->data < element)
                node = RotateLeft(node);
            //右左插入
            else
                node = RotateRightLeft(node);
        }
    }
    return node;    
}
BTNode *GetTreeRoot(BSTree *tree)
{
    return tree->root;
}
void *InsertTree(BSTree *tree, ElementType element)
{
    if(tree->root == NULL)
        tree->root = CreateBTNode(element);
    else
        tree->root = InsertNode(tree->root,element);
}

BTNode *RemoveNodeElement(BTNode *node, ElementType element)
{
    // BTNode *node = FindNodeElement(root,element);
    // if(node == NULL)
    //     return root;
    BTNode *temp = node->parent;
    if(node->left == NULL && node->right == NULL)
    {
        if(node->parent == NULL)
        { 
            node = NULL;
            free(node);
            return temp;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = NULL;
        else
            node->parent->right = NULL;
        free(node);
        return NULL;
    }
    else if(node->left == NULL)
    {
        node->right->parent = node->parent;
        if(node->parent == NULL)
        {
            node = node->right;
            free(node->right);
            return node;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->right;
        else
            node->parent->right = node->right;
        free(node);
        return temp->right;
    }
    else if(node->right == NULL)
    {
        node->left->parent = node->parent;
        if(node == NULL)
        {
            node = node->left;
            free(node->left);
            return node;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->left;
        else
            node->parent->right = node->left;
        free(node);
        return temp->left;
    }
    else
    {
        BTNode *MinNode = node->right;
        while(MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }
        node->data = MinNode->data;
        if(node->right == MinNode)
            node->right = MinNode->right;
        else
            MinNode->parent->left = MinNode->left;
        free(MinNode);
        return node;
    }
}



BTNode *DeleteNode(BTNode *node,ElementType element)
{
    if(node == NULL)
        return NULL;

    if(element < node->data)
    {
        node->left = DeleteNode(node->left,element);
        //右子树重
        if(GetNodeHeight(node->right) - GetNodeHeight(node->left) > 1)
        {
            //右孩子的左子树比右子树高
            //右左
            if(GetNodeHeight(node->right->left) - GetNodeHeight(node->right->right) > 0)
                node = RotateRightLeft(node);
            else
                node = RotateLeft(node);
        }
    }
    else if(element > node->data)
    {
        node->right = DeleteNode(node->right,element);
        //左边重
        if(GetNodeHeight(node->left) - GetNodeHeight(node->right) > 1)
        {
            //左左
            if(GetNodeHeight(node->left->left) - GetNodeHeight(node->left->right) > 0)
                node = RotateRight(node);
            //左右
            else
                node = RotateLeftRight(node);
        }
    }
    //找到要删除的节点
    else
    {
        node = RemoveNodeElement(node,element);
    }
    return node;
}
void *DeleteTree(BSTree *tree, ElementType element)
{
    tree->root = DeleteNode(tree->root,element);
}
